Putin được Tổng thống Yeltsin chỉ định làm chủ tịch (predsedatel, hay thủ tướng) Chính phủ Liên bang Nga vào tháng 8 năm 1999, khiến ông trở thành thủ tướng thứ năm của nước Nga trong khoảng thời gian chưa đầy mười tám tháng. Khi được chỉ định, rất ít người tin rằng Putin, một khuôn mặt rõ ràng ít tiếng tăm, có thể giữ ghế lâu hơn so với những người tiền nhiệm. Những đối thủ chính và có thể là người kế nhiệm của Yeltsin như Thị trưởng Moskva Yuriy Mikhaylovich Luzhkov và cựu Thủ tướng Nga Yevgeniy Maksimovich Primakov đã tiến hành các chiến dịch vận động nhằm thay thế vị tổng thống già yếu, đã có phản ứng mạnh mẽ nhằm ngăn cản Putin xuất hiện với tư cách một đối thủ tiềm năng. Hình ảnh một nhân viên ngành an ninh tiếp cận và xử lý vấn đề khủng hoảng Chechnya (xem bên dưới) một cách cứng rắn của Putin đã nhanh chóng lôi cuốn sự ủng hộ của dân chúng, cho phép ông dần vượt xa các đối thủ. Trong khi chính thức không liên kết với một đảng nào, Putin lại nhận được sự ủng hộ của phe Edinstvo (thống nhất) mới thành lập và hiện chiếm đa số trong cuộc bầu cử Duma tháng 12 năm 1999. Putin được tái chỉ định làm Thủ tướng chính phủ và dường như đang ở vị trí thuận lợi nhất cho cuộc bầu cử tổng thống trong mùa hè sau đó. Quá trình thăng tiến của ông tới chức vụ cao nhất nước Nga thậm chí còn nhanh chóng hơn: ngày 31 tháng 12 năm 1999, Yeltsin bất ngờ từ chức, và theo hiến pháp, Putin được chỉ định làm tổng thống (tạm quyền), trở thành vị tổng thống thứ hai của nhà nước Liên bang Nga. Cuộc bầu cử tổng thống được tổ chức ngày 26 tháng 3 năm 2000, trong đó Putin đã thắng cử ngay từ vòng đầu tiên. Sau này Putin đã trao cho vị cựu tổng thống và gia đình của ông quyền hoàn toàn miễn trừ truy tố (thông qua nghị định tổng thống). Ngay trước đó, Yeltsin và gia đình mình đang bị các cơ quan chức năng Nga và Thụy Sĩ đặt nghi vấn về các trách nhiệm liên quan tới những vụ chuyển tiền bất hợp pháp.

Sau nhiều năm bê bối, thay đổi chính sách liên tục khiến dân chúng bất mãn với Yeltsin - vị tổng thống già cả, vụng về và ốm yếu - thì việc Putin thắng cử và lên nhậm chức đã đánh dấu một bước khởi đầu mới cho nước Nga trong giai đoạn lịch sử hậu Xô viết. Tuy nhiên, việc vị tổng thống mới được thắng cử không tránh khỏi những biện pháp ảnh hưởng hậu trường không nhỏ do nhóm ủng hộ Yeltsin tiến hành, họ đã lựa chọn và ủng hộ Putin nhằm bảo vệ quyền lực riêng cũng như giữ vững các quyền lợi ưu tiên của mình. Khi bộ máy chính phủ mới của Putin hình thành, các bộ mặt nhiều ảnh hưởng cũ thời Yeltsin – gồm cả Lãnh đạo Nhân sự Aleksandr Staliyevich Voloshin và Thủ tướng Mikhail Mikhailovitch Kasyanov – vẫn giữ được nhiều quyền kiểm soát đối với các chính sách và sự chỉ đạo của chính phủ mới. Mặt khác, Putin cũng được hậu thuẫn bởi một nhóm các nhà cải cách kinh tế từ quê hương Sankt-Peterburg của ông, và có thể tin cậy cũng như có được ủng hộ từ siloviki. (Nhóm này được gọi là những thành viên vẫn giữ nhiều quyền lực bên trong các cơ quan an ninh Nga, họ tự coi mình là những người bảo vệ quyền lợi quốc gia khỏi các chính trị gia và các quan chức tham lam, và thường được cung cấp đầy đủ thông tin về mọi mặt đời sống kinh tế, chính trị Nga.) Sự đấu tranh – và hợp tác – giữa nhiều nhóm đó là đặc trưng lớn nhất của nhiệm ký thứ nhất của Tổng thống Putin.

Ngay khi trúng cử, Putin đã đưa ra nhiều biện pháp nhằm tái lập quyền lực tuyệt đối của Kremlin đối với đời sống chính trị Nga. Thời Yeltsin, 89 vùng lãnh thổ chính trị cấp dưới liên bang ở nước Nga (các nước cộng hoà, vùng, krai, Moskva và Sankt-Peterburg) đều được trao những quyền tự trị rất lớn. Trong khi hành động cải cách triệt để này có mục tiêu nhằm giúp cho các thủ đoạn chính trị của Yeltsin trong giai đoạn đầu thập niên 1990, nó cũng dẫn tới tình trạng phá vỡ các quy tắc liên bang và góp phần làm lớn mạnh các phong trào li khai, nổi tiếng nhất như tại Chechnya. Vì thế, một trong những đạo luật đầu tiên của Putin, nhằm tái lập lại cái mà ông gọi là "quyền lực theo chiều dọc" – nghĩa là quay trở lại với hệ thống liên bang từ trên xuống theo truyền thống. Trong hành động đầu tiên, Putin thông báo chỉ định bảy vị "đại diện toàn quyền" của tổng thống. Họ chịu trách nhiệm điều phối hoạt động của liên bang tại các siêu vùng vừa mới được thành lập. Trong khi được coi là hành động thức hai nhằm phá vỡ kiểu nhà nước liên bang thời Yeltsin, vì nhiều lý do hệ thống đại diện toàn quyền đã mang lại một số thành công. Một hành động khác còn mang ý nghĩa quan trọng hơn, Putin cũng đã tiến hành cải cách triệt để hệ thống Thượng viện Nga, Ủy ban Liên bang. Putin và bộ máy của mình trực tiếp đối đầu với nhiều vị Thống đốc bất tuân bị buộc tội tham nhũng, dù không phải lúc nào cũng là người chiến thắng.

Những tháng đầu tiên trong nhiệm kỳ tổng thống thứ nhất của Putin được đánh dấu bằng sự dàn xếp quan hệ với các nhóm tài chính-công nghiệp lớn, mà các nguồn tài chính cũng như các đế chế truyền thông của họ từng là những vũ khí quan trọng trong cuộc chiến tranh chính trị xảy ra trong nước những năm trước đó. Các thành viên chủ chốt trong bộ máy cũ của Yeltsin – thường được gọi thông tục là "the Family" (Gia đình) – quyết tâm trừng phạt phe thất bại, do Vladimir Aleksandrovich Gusinsky, người từng ủng hộ bộ đôi Primakov/Luzhkov cầm đầu. Gusinsky đã rơi vào tình thế nguy ngập từ khi đế chế truyền thông của ông ta liên tục làm ăn thua lỗ và rơi vào tình trạng nợ nần chồng chất, chỉ tồn tại nhờ các khoản trợ cấp từ Gazprom và Ngân hàng Moskva do Luzkhov kiểm soát. Trong vòng một năm từ khi Putin lên nắm quyền, Gusinsky từ lúc là một kẻ có ảnh hưởng trở thành người bị giam vào tù; đế chế truyền thông từng một thời đầy ảnh hưởng của ông (Media-MOST) bị chia rẽ vì phá sản do các mối làm ăn với những công ty nhà nước hay liên minh với nhà nước bị hủy bỏ cũng như dưới sức nặng của những phán quyết hình sự hay dân sự do tòa án đưa ra. Thành tích ấn tượng nhất của Putin trong nhiệm kỳ tổng thống thứ nhất là ngay khi vừa lên cầm quyền ông đã vực dậy nền kinh tế Nga từ chỗ suy thoái nhiều năm liền chuyển sang tăng trưởng. Nước Nga bắt đầu hồi sinh dưới sự lãnh đạo của Putin.

Cuộc khủng hoảng lớn nhất Putin phải đối mặt trên cương vị tổng thống xảy ra tháng 8 năm 2000, khi chiếc tàu ngầm nguyên tử Nga Kursk đắm ngoài khơi bán đảo Kola, làm thiệt mạng 118 thủy thủ trên tàu. Rất nhiều người thuộc đủ mọi tầng lớp trong xã hội Nga tức giận với sự thất bại của chính phủ và quân đội trong việc cung cấp những thông tin đáng tin cậy về mức độ và sự chắc chắn của thảm họa trong những ngày đầu tiên. Sau nhiều ngày để dân chúng tức giận và ngày càng hoang mang, Putin cắt ngắn kì nghỉ của mình, quay trở lại Moskva nhận trách nhiệm trực tiếp giải quyết cuộc khủng hoảng. Cho tới khi chiếc tàu ngầm được kéo lên, ủy ban điều tra của chính phủ về vụ tai nạn này đã đưa ra rất nhiều giả thuyết về nguyên nhân, gồm cả việc va chạm với tàu ngầm của NATO (một giả thuyết không bao giờ được các bằng chứng ủng hộ và bị các nước thuộc liên minh bác bỏ). Tuy Putin bị chỉ trích trên các phương tiện thông tin đại chúng Nga vì sự bất lực của mình trong những giai đoạn đầu cuộc khủng hoảng, nhưng nó không để lại những hậu quả lâu dài đối với hình ảnh ông trong lòng nhân dân.

Putin không ủng hộ việc xóa bỏ quá khứ Liên bang Xô viết ra khỏi lịch sử nước Nga — vốn là chính sách trước kia của Yeltsin nhằm mục đích chính là đối phó với các đối thủ của Đảng Cộng sản Nga. Ông đã miêu tả niềm tin của mình rằng Liên Xô trước kia là một phần quan trọng trong lịch sử Nga và những di sản của Liên Xô có một ảnh hưởng lớn trên việc hình thành xã hội Nga hiện đại. Vì thế, Putin đã đưa một số biểu tượng thời Xô viết đã quay trở lại nước Nga, như thương hiệu lá cờ đỏ của Hồng quân, tiêu ngữ "Ngôi sao Xô Viết", và Quốc ca Liên Xô (được sửa chữa lời nhưng giữ nguyên nền nhạc) – tất cả những thứ đó đã tạo được ấn tượng tốt với đa số dân chúng Nga. Trả lời những người chỉ trích các hành động đó, Putin đã đưa ra lý lẽ rằng ông là tổng thống của mọi người Nga - gồm cả những người về hưu đã mất mọi thứ cùng với sự chuyển tiếp thời hậu Xô viết, những người vẫn trung thành với những biểu tượng của quá khứ.

Đảng Nước Nga thống nhất ủng hộ Putin đã giành được một thắng lợi vô tiền khoáng hậu trong cuộc Bầu cử Nghị viện Nga 2003. Các nhà quan sát chính thức từ nước ngoài đã gọi đó là một cuộc bầu cử tự do nhưng ghi chú rằng các cơ quan truyền thông lớn do nhà nước kiểm soát, đặc biệt là Truyền hình quốc gia Nga, đã tiến hành các chiến dịch truyền thông rộng lớn và không công bằng dành riêng cho đảng cầm quyền. Quả vậy, đa số các đài truyền hình Nga hiện dưới quyền quản lý trực tiếp hay gián tiếp của Kremlin. Trong khi có số độc giả hạn chế hơn, các tờ báo hiện đa dạng hơn; một số tờ chỉ trích chính phủ Kremlin, trong khi số khác ủng hộ đường lối chính phủ. Một trong hai tờ báo thương mại chính chính, Kommersant, do Boris Abramovich Berezovsky trực tiếp kiểm soát, trong khi tờ kia – tờ Vedomosti vốn được độc giả rất tin tưởng – thuộc sự đồng sở hữu của hai tờ Financial Times và Wall Street Journal.

Những lời chỉ trích trong nước và quốc tế buộc tội Putin đã đạo diễn các phiên tòa xử các nhân vật đầu sỏ chính trị như Boris Abramovich Berezovsky, Vladimir Aleksandrovich Gusinsky, và sau này là Mikhail Borisovich Khodorkovsky như một phần trong nỗ lực của Kremlin nhằm kiểm soát toàn bộ phương tiện truyền thông Nga và các lĩnh vực quan trọng trong nền kinh tế Nga. Về phần mình, chính quyền của Putin đã đưa ra lý lẽ rằng những hành động của họ chống lại các nhân vật đầu sỏ trên dựa trên tinh thần pháp luật và nhằm kìm chế cũng như hủy bỏ những vấn đề xung đột nghiêm trọng trong nền kinh tế Nga sau nhiều năm có được đặc quyền đặc lợi.

Ngày 24 tháng 2 năm 2004, chưa tới một tháng trước cuộc bầu cử, Putin đã cách chức Thủ tướng Kasyanov và toàn bộ chính phủ Nga và chỉ định Viktor Borisovich Khristenko làm quyền thủ tướng. Ngày 1 tháng 3, ông chỉ định Mikhail Yefimovich Fradkov vào vị trí này.